package LeetCode.Arrays;

/**
 * @author : LdLtd
 * @Date : 2023/8/6
 * @Description:41. 缺失的第一个正数
 */
public class first_missing_positive {
    class Solution {
            /*hash表，先把负数标记为n+1，然后所有数都是正数
            * 如果nums[i]在n中，标记nums[nums[i]-1]为负数
            * 遍历第一个正数+1*/
        public int firstMissingPositive1(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; ++i) {
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }
            for (int i = 0; i < n; ++i) {
                if (nums[i] != i + 1) {
                    return i + 1;
                }
            }
            return n + 1;
        }
        /*置换，把数组还原，Index对应值，然后第一个不相等的即为最大，如果nums[i]》n或者小于0就不管*/
        public int firstMissingPositive(int[] nums) {
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                while(nums[i]>0&&nums[i]<=length&&nums[nums[i]-1]!=nums[i]){
                    int t=nums[nums[i]-1];
                    nums[nums[i]-1]=nums[i];
                    nums[i]=t;
                }
            }
            for (int i = 0; i < length; i++) {
                if(nums[i]!=i+1){
                    return i+1;
                }
            }
            return length+1;
        }
    }
}
